"""
爬楼梯：斐波那契数列
方法：
1、递推（超时）
2、循环
3、记忆化递归，自顶向下
4、dp，自底向上
3和4都是用数组暂存算过的值



假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

"""


# 斐波那契数列：递归。时间复杂度o(2^n)
# def climb(n: int) -> int:
#     if n == 1 or n == 0:
#         return 1
#     return climb(n - 1) + climb(n - 2)


# 循环，自底向上迭代。时间复杂度o(n),空间复杂度o(1)
def climb(n: int) -> int:
    a = b = 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b


print(climb(10))
